package com.kk.datastructure.stack.calculatro;

/**
 * title: 栈实现综合计算器
 * @author 阿K
 * 2020年11月29日 下午3:30:14 
 */
public class Calculatro {
	public static void main(String[] args) {
		// expression 表达式
		String expression = "30-8*4/2";
		// 创建两个栈，一个数栈，一个符号栈
		StackArray numStack = new StackArray(10);
		StackArray operStack = new StackArray(10);
		// 定义需要的相关变量
		int index = 0;// //用于扫描
		int num1 = 0; 
		int num2 = 0;
		int oper = 0;
		int res = 0;
		char ch = ' '; // 将每次扫描得到char保存到ch
		String keepNum = ""; // 用于拼接 多位数
		// 开始while循环的扫描expression
		while (true) {
			// 依次得到expression 的每一个字符
			ch = expression.substring(index, index + 1).charAt(0);
			// 判断ch是什么，然后做相应的处理
			if (operStack.isOper(ch)) {// 如果是运算符
				// 判断当前的符号栈是否为空
				if (!operStack.isEmpty()) {
					if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
						// 如果符号栈有操作符，就进行比较
						// 比较规则：如果当前操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数来
						// 再从符号栈中pop出一个操作符，进行运算，将得到的结果入数栈，然后将当前操作符入符号栈
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = numStack.cal(num1, num2, oper);
						// 将运算结果，入数栈
						numStack.push(res);
						// 操作符入操作符栈
						operStack.push(ch);
					} else {
						// 如果当前操作符优先级大于操作符栈顶的值优先级，则直接入操作符栈
						operStack.push(ch);
					}
				} else {
					// 如果操作符栈为空，则直接入栈
					operStack.push(ch);
				}
			} else {// 如果是数，则入数栈
				
				//numStack.push(ch - 48); //? "1+3" '1' => 1
				// 1、在处理多位数的时候，不能遇到数就直接入栈，因为可能数多位数
				// 2、在处理数时，需要向expression 表达式的 index 再往后移动 一位看 一下，如果是数 则继续扫描，
				//如果遇到的是符号，就可以直接入数栈了
				// 3、因此需要一个辅助的字符串拼接判断
				
				keepNum +=ch;// 处理多位数
				
				// 如果ch已经是expression的最后一位，就直接入栈
				if(index == expression.length() -1) {
					numStack.push(Integer.valueOf(keepNum));
				}else {
					// 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
					// 注意是看后一位，不是index++
					if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
						// 如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
						numStack.push(Integer.valueOf(keepNum));
						// 清空（注意！！！）
						keepNum = "";
					}
				}
			}
			// 让index + 1, 并判断是否扫描到expression最后
			index++;
			if(index >= expression.length()) {
				break;
			}
		}
		
		// 当表达式扫描计算完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行
		while(true) {
			// 如果符号栈为空，则计算到最后的结果, 数栈中只有一个数字【结果】
			if(operStack.isEmpty()) {
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(num1, num2, oper);
			numStack.push(res);//入栈	
		}
		// 将数栈的最后数，pop出，就是结果
		int result = numStack.pop();
		System.out.printf("表达式 %s = %d", expression, result);
	}
}


//定义一个 StackArray 表示栈
class StackArray {
	private int maxSize;// 栈的大小
	private int[] stack;// 数组，数组模拟栈，数据就放在该数组
	private int top = -1;// top表示栈顶的角标，初始化为-1

	// 构造器
	public StackArray(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	
	// 查看栈顶的值，不是pop
	public int peek() {
		return stack[top];
	}

	// 返回运算符优先级，数字越大，优先级越高
	public int priority(int oper) {
		if(oper == '*' || oper == '/') {
			return 2;
		}
		else if(oper == '+' || oper == '-') {
			return 1;
		}
		return -1;// 不满足的情况
	}
	
	// 判断是否为一个运算符
	public boolean isOper(char val) {
		return val == '+' || val == '-' || val == '*' || val == '/';
	}
	
	// 计算方法
	public int cal(int num1,int num2,int oper) {
		int res = 0; // res 用于存放计算的结果
		switch (oper) {
		case '+':
			res = num1+num2;
			break;
		case '-':
			res = num2-num1;
			break;
		case '*':
			res = num1*num2;
			break;
		case '/':
			res = num2/num1;
			break;
		default:
			break;
		}
		return res;
	}
		
	// 栈满
	public boolean isFull() {
		// return stack.length == maxSize;
		return top == maxSize - 1;
	}

	// 栈空
	public boolean isEmpty() {
		return top == -1;
	}

	// 入栈-push
	public void push(int data) {
		// 判断是否满
		if (isFull()) {
			System.out.println("栈满");
			return;
		}
		top++;
		stack[top] = data;
	}

	// 出栈-pop,将栈顶的数据返回
	public int pop() {
		// 判断是否为空
		if (isEmpty())
			throw new RuntimeException("栈空，无法取！！");

		return stack[top--];
	}

	// 遍历栈
	public void list() {
		// 判空
		if (isEmpty())
			System.out.println("当前栈没有数据，无法遍历");
		for (int i = top; i >= 0; i--) {
			System.out.printf("stack[%d]=%d\n", i, stack[i]);
		}
	}
}

